package ACwing.P3SearchandGraph.DFS;

import java.util.Scanner;

/**
 * @Date : 2023-04-02
 * @Description:843. n-皇后问题
 * 截距要么是 b=y+x  要么是b=y-x  可能为负 +n偏移量  b=
 */
public class NQueen {
    static int n;
    static int N = 20;
    static char[][] g = new char[N][N];  //记录图
    static boolean[] row = new boolean[N];//行可用
    static boolean[] col = new boolean[N];  //列可用
    static boolean[] dg = new boolean[N];  //正对角线
    static boolean[] udg = new boolean[N];//反对角线

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                g[i][j] = '.';
            }
        }
        //dfs1(0);//从第一行开始
        dfs2(0, 0, 0);//从第一格开始，放了0个棋
    }

    //方案1   默认每一行只放一个
    static void dfs1(int u) {
        //搜索完毕
        if (u == n) writeto();

        for (int i = 0; i < n; i++) {
            //列 对角线都可以放
            if (!col[i] && !dg[u + i] && !udg[i - u + n]) {
                g[u][i] = 'Q';
                col[i] = dg[u + i] = udg[i - u + n] = true;
                dfs1(u + 1);  //搜索下一层
                col[i] = dg[u + i] = udg[i - u + n] = false;
                g[u][i] = '.';//恢复
            }
        }


    }

    //方案2  一个格子一个格子的搜索，每个格子有放或者不放两种可能
    static void dfs2(int x, int y, int s) {
        if (y == n) {  //判断到横行最后一格出界时，判断下一行同时回到左边起点
            y = 0;
            x++;
        }
        if (x == n) {//如果判断到最后一行
            if (s == n) writeto();//如果摆完了
            return;
        }

        //不放皇后
        dfs2(x, y + 1, s);//直接去下一格子
        //放皇后  行列对角线都可以放
        if (!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n]) {
            //修改状态
            g[x][y] = 'Q';
            row[x] = col[y] = dg[x + y] = udg[x - y + n] = true;
            //去下一个格子
            dfs2(x, y + 1, s + 1);
            //恢复现场
            g[x][y] = '.';
            row[x] = col[y] = dg[x + y] = udg[x - y + n] = false;
        }


    }

    private static void writeto() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.print(g[i][j]);
            }
            System.out.println();
        }
        System.out.println();
    }
}